package com.leetcode.partition5;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/23 13:41
 */
public class LC413等差数列拆分 {

    public static int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3) return 0;
//        return slidingWindow(nums);
        return dynamicProgramming(nums);
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
//        int[] nums = {2, 1, 3, 4, 2, 3};
        System.out.println(numberOfArithmeticSlices(nums));
    }

    private static int dynamicProgramming(int[] nums) {
        int answer = 0;
        //dp[i]代表子数组nums[0]到nums[i]等差数列的个数
        int[] dp = new int[nums.length];
        for (int i = 2; i < nums.length; i++) {
            //等差数列必要条件
            if (nums[i - 1] - nums[i - 2] == nums[i] - nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
                answer += dp[i];
            }
        }
        System.out.println(Arrays.toString(dp));
        return answer;
    }

    private static int slidingWindow(int[] nums) {
        int answer = 0, preDiff = nums[1] - nums[0], size = 2;
        for (int i = 2; i < nums.length; i++) {
            int curDiff = nums[i] - nums[i - 1];
            if (preDiff == curDiff) {           //满足等差数列的条件，将该元素加入到滑动窗口中
                size++;
                continue;
            }
            answer += (size - 1) * (size - 2) >> 1;     //加入结果，重置size，重新收集等差数列的元素
            size = 2;
            preDiff = curDiff;
        }
        answer += (size - 1) * (size - 2) >> 1;
        return answer;
    }
}
